package algorithm;

public class leetcode_0494 {

    public int findTargetSumWays(int[] nums, int target) {
        int len=nums.length;
        if(len==1) {
            if(nums[0]==target||nums[0]+target==0) return 1;
            return 0;
        }
        int sum=0;
        for(int i=0;i<len;++i){
            sum+=nums[i];
        }
        sum-=target;
        if(sum%2==1||sum<0) return 0;
        sum/=2;
        int [][] dp=new int[len+1][sum+1];
        dp[0][0]=1;
        for(int i=1;i<=len;++i){
            if(nums[i-1]==0) dp[i][0]=dp[i-1][0]*2;
            else dp[i][0]=dp[i-1][0];
        }
        dp[0][0]=1;
        for(int i=1;i<=len;++i){
            for(int j=0;j<=sum;++j){
                dp[i][j]+=dp[i-1][j];
                if(j>=nums[i-1]) dp[i][j]+=dp[i-1][j-nums[i-1]];
            }
        }
        return dp[len][sum];
    }
}
